package gold.digger;

import org.apache.commons.lang.StringUtils;

import java.util.*;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC966 {
    public long startExecuteTime = System.currentTimeMillis();


    /*
    * @param 此题目参考了别人代码
    * 这是因为问题情况较为复杂
    * 早知道早点看答案了，太™欺负人的题目了
    * @return:
    */
    class Solution {
        Set<String> words_perfect;
        Map<String, String> words_cap;
        Map<String, String> words_vow;

        public String[] spellchecker(String[] wordList, String[] queries) {
            words_perfect = new HashSet();
            words_cap = new HashMap();
            words_vow = new HashMap();

            for (String word : wordList) {
                words_perfect.add(word);

                String wordLowercase = word.toLowerCase();
                words_cap.putIfAbsent(wordLowercase, word);

                String wordLowerDV = devowel(wordLowercase);
                words_vow.putIfAbsent(wordLowerDV, word);
            }

            String[] ans = new String[queries.length];
            int t = 0;
            for (String query : queries)
                ans[t++] = solve(query);
            return ans;
        }

        public String solve(String query) {
            if (words_perfect.contains(query))
                return query;

            String queryL = query.toLowerCase();
            if (words_cap.containsKey(queryL))
                return words_cap.get(queryL);

            String queryLV = devowel(queryL);
            if (words_vow.containsKey(queryLV))
                return words_vow.get(queryLV);

            return "";
        }

        public String devowel(String word) {
            StringBuilder ans = new StringBuilder();
            for (char c : word.toCharArray())
                ans.append(isVowel(c) ? '*' : c);
            return ans.toString();
        }

        public boolean isVowel(char c) {
            return (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u');
        }
    }


    class Solution_Fail_for_Complexity {
        public Map<String, Set<String>> dict = new LinkedHashMap<>();
        public Map<Integer, Set<Character>> posDict = new LinkedHashMap<>();
        public Set<Character> vowelSet = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));

        public String[] spellchecker(String[] wordList, String[] queries) {
            for (String word : wordList) {
                String wordKey = word.toLowerCase();
                if (dict.containsKey(wordKey)) dict.get(wordKey).add(word);
                else {
                    Set<String> set = new LinkedHashSet<>();
                    set.add(word);
                    dict.put(wordKey, set);
                }
            }

            String[] res = new String[queries.length];
            for (int i = 0; i < queries.length; i++) {
                res[i] = getQueryRes(queries[i].toCharArray(), 0);
            }

            return res;
        }

        public String getQueryRes(char[] queryArray, int curPos) {
            if (curPos >= queryArray.length) return "";
            String query = new String(queryArray);
            String queryKey = curPos > 0 ? query : query.toLowerCase();
            queryArray = curPos == 0 ? queryArray : queryKey.toCharArray();
            String queryRes = "";

            if (dict.containsKey(queryKey)) {
                if (dict.get(queryKey).contains(query)) queryRes = query;
                else queryRes = dict.get(queryKey).iterator().next();
                return queryRes;
            }

            boolean matchFlag = false;
            for (int j = curPos; j < queryArray.length; j++) {
                char ch = queryArray[j];
                if (vowelSet.contains(ch)) {
                    for (char vowel : vowelSet) {
                        if (vowel == ch) continue;
                        queryArray[j] = vowel;
                        queryKey = new String(queryArray);
                        if (dict.containsKey(queryKey)) {
                            queryRes = dict.get(queryKey).iterator().next();
                            matchFlag = true;
                            break;
                        }

                        String recursiveQuery = getQueryRes(queryArray, j + 1);
                        if (!recursiveQuery.equals("")) {
                            queryRes = recursiveQuery;
                            matchFlag = true;
                            break;
                        }

                        queryArray[j] = ch;//switch back.
                    }
                }

                if (matchFlag) break;
            }
            return queryRes;
        }
    }


    //Input: wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
//Output: ["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
    public void run() {
        Solution solution = new Solution();
        String[] wordlist = {"KiTe", "kite", "hare", "Hare"};
        String[] queries = {"kite", "Kite", "KiTe", "Hare", "HARE", "Hear", "hear", "keti", "keet", "keto"};
        String[] res = solution.spellchecker(wordlist, queries);
        for (String re : res) {
            if (StringUtils.isBlank(re)) System.out.print("blank" + " -- ");
            else System.out.print(re + " -- ");
        }
    }

    public static void main(String[] args) throws Exception {
        LC966 an = new LC966();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
